package com.zp.self.module.level_4_算法练习.数据结构.二叉树.平衡二叉树;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ：by Zeng Peng
 * @date ：Created 2022/6/2 21:51
 * @description ：验证是否是平衡二叉树
 */
public class 平衡二叉树_验证 {

    @Test
    public  void checkAVL(){

        int[] arr = new int[]{1, 4, 5, 6, 7, 10, 9, 8, 23, 2, 13, 32, 321, 32, 321, 312, 321, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 23, 2};
        AvlNode node = 平衡二叉树_插入_构建.buildAVL(arr);
        //验证平衡二叉树
        Map<AvlNode,Integer> map = new HashMap<>();
        System.out.println("是否是AVL: "+isAVL(node,map));
    }

    /**
     题目：验证二叉树是否是 平衡二叉树

     分析：
         1.递归遍历每个节点，得到每个节点的左右节点高度、节点值大小是否符合平衡二叉树
         2.成员遍历记录是否出现不符合的情况，最后返回值是否为true

     边界值 & 注意点：
     1.
     **/
    public static boolean isAVL(AvlNode node, Map<AvlNode, Integer> map) {
        if(node==null)
            return true;
        if(node.lchild!=null && node.lchild.data>node.data)
            return false;
        if(node.rchild!=null && node.rchild.data<node.data)
            return false;
        int lh = getHeight(node.lchild,map);
        int rh = getHeight(node.rchild,map);
        map.put(node,Math.max(rh,lh)+1);
        if(Math.abs(lh-rh)>1)
            return false;
        return  isAVL(node.lchild,map)&& isAVL(node.rchild,map);
    }

    /**
     * Description: 得到每个节点的左右节点高度,防止重复递归，使用map存储
     */
    private static int getHeight(AvlNode node, Map<AvlNode, Integer> map) {
        if(node==null)
            return 0;
        if(map.containsKey(node))
            return map.get(node);
        map.put(node,Math.max(getHeight(node.lchild,map),getHeight(node.rchild,map))+1);
        return map.get(node);
    }
}
